package com.cory.utils.algorithm;

import java.lang.reflect.Array;

/**
 * 排序算法
 * @author xc
 * @version 2017-02-17
 */
@SuppressWarnings("unchecked")
public class SortUtils {

	/**
	 * 冒泡排序
	 * 每次比较相邻的2个元素，把大的往后移
	 */
	public static <T extends Comparable<T>> void bubbleSort(Comparable<T>[] array) {
		int size = array.length;
		Comparable<T> temp = null;
		for (int i = 0; i < size - 1; i++) {
			for (int j = 0; j < size -1 - i; j++) {
				if (array[j].compareTo((T)array[j + 1]) > 0) {
					temp = array[j];
					array[j] = array[j + 1];
					array[j + 1] = temp;
				}
			}
		}
	}
	
	/**
	 * 选择排序
	 * 每次循环找到做小的元素放到起始位置
	 */
	public static <T extends Comparable<T>> void selectSort(Comparable<T>[] array) {
		int size = array.length;
		Comparable<T> temp = null;
		for (int i = 0; i < size; i++) {
			int k = i;
			for (int j = i + 1; j < size; j++) {
				if (array[k].compareTo((T)array[j]) > 0) {
					k = j;
				}
			}
			if (k != i) {
				temp = array[k];
				array[k] = array[i];
				array[i] = temp;
			}
		}
	}
	
	/**
	 * 插入排序
	 * 每次循环将一个待排序的元素，按其大小插入到前面已经排序好序列的合适位置
	 */
	public static <T extends Comparable<T>> void insertSort(Comparable<T>[] array) {
		int size = array.length;
		Comparable<T> temp = null;
		for (int i = 1; i < size; i++) {
			temp = array[i];
			int j = i;
			while (j > 0 && array[j - 1].compareTo((T)temp) > 0) {
				array[j] = array[j - 1];
				j--;
			}
			array[j] = temp;
		}
	}
	
	/**
	 * 归并排序
	 * 递归将序列分解成2个子序列进行排序，在将排序好的子序列合并
	 */
	public static <T extends Comparable<T>> void mergeSort(Comparable<T>[] array) {
		Comparable<T>[] temp = (Comparable[])Array.newInstance(Comparable.class, array.length);
		mergeSort(array, 0, array.length - 1, temp);
	}
	
	private static <T extends Comparable<T>> void mergeSort(Comparable<T>[] array, int low, int high, Comparable<T>[] temp) {
		if (low < high) {
			int mid = (low + high) / 2;
			mergeSort(array, low, mid, temp);
			mergeSort(array, mid + 1, high, temp);
			
			int m = low, n = mid + 1;
			int size = high - low + 1;
			for (int k = 0; k < size; k++) {
				if (n <= high && (m > mid || array[m].compareTo((T)array[n]) > 0)) {
					temp[k] = array[n++];
				} else {
					temp[k] = array[m++];
				}
			}
			for (int k = 0; k < size; k++) {
				array[low + k] = temp[k];
			}
		}
	}
	
	/**
	 * 希尔排序
	 * 先将整个序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序
	 */
	public static <T extends Comparable<T>> void shellSort(Comparable<T>[] array) {
		int size = array.length;
		Comparable<T> temp = null;
		for (int increment = size >>> 1; increment >= 1; increment >>>= 1) {
			for (int group = 0; group < increment; group++) {
				for (int i = group + increment; i < size; i = i + increment) {
					temp = array[i];
					int j = i;
					while (j > group && array[j - increment].compareTo((T)temp) > 0) {
						array[j] = array[j - increment];
						j = j - increment;
					}
					array[j] = temp;
				}
			}
		}
	}
	
	/**
	 * 快速排序
	 * 将记录分割成独立的两部分，其中一部分记录的数据均比另一部分数据小，则分别对这两部分继续进行排序，直到整个序列有序
	 */
	public static <T extends Comparable<T>> void quickSort(Comparable<T>[] array) {
		quickSort(array, 0, array.length - 1);
	}
	
	private static <T extends Comparable<T>> void quickSort(Comparable<T>[] array, int low, int high) {
		if (low < high) {
			Comparable<T> key = array[low];
			int m = low, n = high;
			
			while (m < n) {
				while (m < n && key.compareTo((T)array[n]) <= 0) {
					n--;
				}
				array[m] = array[n];
				while (m < n && key.compareTo((T)array[m]) >= 0) {
					m++;
				}
				array[n] = array[m];
			}
			array[m] = key;
			
			quickSort(array, low, m -1);
			quickSort(array, m + 1, high);
		}
	}
	
	/**
	 * 堆排序
	 * 一种树形选择排序，是对直接选择排序的有效改进，每次将最大值放入树根节点在和序列尾的元素交换
	 */
	public static <T extends Comparable<T>> void heapSort(Comparable<T>[] array) {
		int size = array.length;
		for (int i = (size >>> 1) - 1; i >= 0; i--) {
			heapBuild(array, i, size);
		}
		
		Comparable<T> max = null;
		for (int i = 1; i < size; i++) {
			int k = size - i;
			
			max = array[0];
			array[0] = array[k];
			array[k] = max;
			
			heapBuild(array, 0, k);
		}
	}
	
	private static <T extends Comparable<T>> void heapBuild(Comparable<T>[] array, int index, int size) {
		Comparable<T> temp = null, node = array[index];
		int j = index;
		while (j < (size >>> 1)) {
			int left = (j << 1) + 1, right = left + 1;
			temp = array[left];
			if (right < size && temp.compareTo((T)array[right]) < 0)
				temp = array[left = right];
			if (node.compareTo((T)temp) >= 0)
				break;
			array[j] = temp;
			j = left;
		}
		array[j] = node;
	}
	
}
